UVa/10261 - Ferry loading/10261.2.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <map>
  19 #include <set>
  20
  21 #define D(x) cout << #x " is " << x << endl
  22
  23 /*
  24   dp[i][j] = Verdadero si puedo repartir los primeros i carros en orden tal que en el port haya j centímetros usados.
  25   (El Starboard tendría entonces sum[i] - j unidades usadas)
  26 */
  27 bool dp[205][10005];
  28 int choice[205][10005], w[205], sum[205];
  29
  30 int main(){
  31
  32   int C;
  33   cin >> C;
  34   bool print_stupid_empty_line = false;
  35
  36   while(C--){
  37     if (print_stupid_empty_line) cout << endl;
  38     print_stupid_empty_line = true;
  39
  40     int length;
  41     cin >> length;
  42     length *= 100;
  43
  44     int n = 1;
  45     w[0] = sum[0] = 0;
  46     for (int x; cin >> x && x; ){
  47       if (n <= 200){
  48         w[n] = x;
  49         sum[n] = sum[n-1] + w[n];
  50         ++n;
  51       }
  52     }
  53     --n;
  54
  55     pair<int, int> ans;
  56
  57     memset(dp, 0, sizeof dp);
  58     memset(choice, -1, sizeof choice);
  59
  60     dp[0][0] = true;
  61     for (int i=0; i<n; ++i){
  62       for (int j=0; j<=length; ++j){
  63         if (dp[i][j]){
  64           if ((j + w[i+1]) <= length){
  65             dp[i+1][j + w[i+1]] = true;
  66             choice[i+1][j + w[i+1]] = 1;
  67             ans = make_pair(i+1, j + w[i+1]);
  68           }
  69
  70           if ((sum[i] - j + w[i+1]) <= length){
  71             dp[i+1][j] = true;
  72             choice[i+1][j] = 0;
  73             ans = make_pair(i+1, j);
  74           }
  75         }
  76       }
  77     }
  78
  79     cout << ans.first << endl;
  80     string output = "";
  81     for (int i=ans.first, j=ans.second; i>0 && choice[i][j] != -1; --i){
  82       output = (choice[i][j] ? "port\n" : "starboard\n" ) + output;
  83       if (choice[i][j]) j -= w[i];
  84     }
  85     cout << output;
  86
  87   }
  88   return 0;
  89 }